package com.wang.utils.linklist;

/**
 * @author 10570
 * @date 2021/7/14 23:36
 */

import java.sql.SQLOutput;
import java.util.LinkedList;

/**
 * 双向链表
 */
public class DoubleLinkListDemo {
    public static void main(String[] args) {
        LinkedList l = new LinkedList();
        DoubleLinkList linkedList = new DoubleLinkList();
        System.out.println("双向联表的测试");
        HeroNode2 heroNode1 = new HeroNode2(1,"宋江","及时雨");
        HeroNode2 heroNode2 = new HeroNode2(2,"lujunyi","玉麒麟");
        HeroNode2 heroNode3 = new HeroNode2(3,"吴用","智多星");
        HeroNode2 heroNode4 = new HeroNode2(4,"林冲","豹子头");
      /*  linkedList.add(heroNode3);
        linkedList.add(heroNode1);
        linkedList.add(heroNode2);
        linkedList.add(heroNode4);
        linkedList.show();
        HeroNode2 newHeroNode = new HeroNode2(4,"公孙胜","入云龙");
        linkedList.update(newHeroNode);
        System.out.println("修改后打印");
        linkedList.show();
        linkedList.delete(2);

        System.out.println("删除后的结果");
        linkedList.show();
        //按序插入*/
        System.out.println("按序插入");
        linkedList.addByOrder(heroNode2);
        linkedList.addByOrder(heroNode1);
        linkedList.addByOrder(heroNode4);
        linkedList.addByOrder(heroNode3
        );
        linkedList.show();
    }
}

class DoubleLinkList{
    /**
     * 1、遍历是一样的
     * 2、添加默认在双向的最后
     *  1）先找到最后一个节点
     *  2）temp.next = newHeroNode
     *  3）newHeroNode.pre = temp
     * 3、修改原理一样
     * 4、删除
     *  1）可以实现自我删除
     *  2）直接找到眼删除的节点，temp
     *  3）temp.pre.next = temp.next
     *  4）temp.next.pre = temp.pre
     */
    //按编号顺序添加
    public void addByOrder(HeroNode2 heroNode){
        //因为头节点不动，需要辅助变量来找到位置
        //找到位置为添加位置的前一个节点
        HeroNode2 temp = head;
        boolean flag = false;
        boolean flag2 = false;
        while (true){
            if (temp.root > heroNode.root) {
                break;
            }else if (temp.next == null) {
                flag2 = true;
                break;
            }else if (temp.root == heroNode.root){
                flag = true;
            }
            temp = temp.next;
        }
        if (flag2){
            temp.next = heroNode;
            heroNode.pre = temp;
        }else if (flag){
            System.out.println("编号已存在");
        }else {
            heroNode.next = temp;
            temp.pre.next = heroNode;
            heroNode.pre = temp.pre;
            temp.pre = heroNode;
        }

    }


    //先定义一个头节点
    private HeroNode2 head = new HeroNode2(0,"","");
    //返回头节点
    public HeroNode2 getHead() {
        return head;
    }

    public void setHead(HeroNode2 head) {
        this.head = head;
    }

    public void add(HeroNode2 heroNode2){
        //head节点不动  需要一个辅助遍历  temp
        HeroNode2 temp = head;
        while (true){
            //找到链表的最后
            if (temp.next == null){
                break;
            }
            //如果没有找到后移
            temp = temp.next;
        }
        //退出循环时，temp指向链表的最后
        //添加一个节点到双向联表的最后
        temp.next = heroNode2;
        heroNode2.pre = temp;
    }

    //删除节点
    //1、辅助变量，找到要删除的节点的前一个节点
    //2、temp.next = temp.next.next
    //将temp.next.root 与需要删除的节点的root比较
    //3、被删除的节点没有其他引用，将会被gc回收

    /**
     * 删除逻辑
     * 1、可以直接找删除的节点，找到后自我删除
     * @param root
     */
    public void delete(int root){
        boolean flag = false;
        //判空
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }
        HeroNode2 temp = head.next; //指向要删除的节点

        while (true){
            if (temp == null){  //已经到最后一个节点
                break;
            }
            if (temp.root == root){
                //找到要删除的节点的前一个节点temp
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            //找到可以删除,自我删除
            temp.pre.next = temp.next;
            //有风险，删除最后一个节点
            //temp.next 会为空
            //最后一个节点就不执行
            if (temp.next != null){
                temp.next.pre = temp.pre;
            }
        }else {
            System.out.printf("没有找到要删除的节点%d",root);
        }

    }

    //修改节点信息根据编号来修改，编号不变
    //内容修改和单向一样，节点类型不同
    public void update(HeroNode2 newHeroNode){
        //根据heroNode.root来修改
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }
        //定义辅助 变量
        HeroNode2 temp = head.next;
        boolean flag = false; // 表示是否找到节点
        while (true){
            if (temp == null){
                System.out.println("倒了链表最后");
                break;
            }
            if (temp.root == newHeroNode.root){
                flag = true;
                break;
            }
            temp = temp.next;


        }
        if (flag){
            temp.name = newHeroNode.name;
            temp.nickName = newHeroNode.nickName;
        }else {
            System.out.printf("没有找到编号为%d，不能修改",newHeroNode.root);
        }
    }

    //显示链表
    public void show(){
        //先判断链表是否为空
        if (head.name == null){
            System.out.println("链表为空");
            return;
        }
        //头节点不能动，因此需要一个辅助变量遍历
        HeroNode2 temp = head.next;

        while (true){
            //判断是否为空
            if (temp == null){
                break;
            }
            System.out.println(temp);
            //将next后移
            temp = temp.next;
        }
    }


}

//定义heroNode
class HeroNode2{
    int root;
    String name;
    String  nickName;
    HeroNode2 next;  //指向下一个节点
    HeroNode2 pre;  //指向上一个节点


    @Override
    public String toString() {
        return "HeroNode2{" +
                "root=" + root +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
//                ", next=" + next +
//                ", pre=" + pre +
                '}';
    }

    public HeroNode2(){
    }
    public HeroNode2(int root, String name, String nickName) {
        this.root = root;
        this.name = name;
        this.nickName = nickName;
    }
    //重写toString（）


}
